package problems.daily;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * 1263. 推箱子
 * <p>https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/</p>
 *
 * @author dubulingbo, 2023/05/08, 008 20:46.
 */
public class DT1263 {
    public int minPushBox(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 玩家位置
        int sx = -1, sy = -1;
        // 箱子位置
        int bx = -1, by = -1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'S') {
                    sx = i;
                    sy = j;
                } else if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                }
            }
        }

        int[] dir = {0, -1, 0, 1, 0};
        Queue<int[]> que = new ArrayDeque<>();
        int[][] dis = new int[m * n][m * n];

        for (int i = 0; i < m * n; ++i)
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        dis[sx * n + sy][bx * n + by] = 0;
        que.offer(new int[]{sx * n + sy, bx * n + by});

        while (!que.isEmpty()) {
            Queue<int[]> assQue = new ArrayDeque<>();
            while (!que.isEmpty()) {
                int[] pos = que.poll();
                int spos = pos[0], bpos = pos[1];
                int curSx = spos / n, curSy = spos % n;
                int curBx = bpos / n, curBy = bpos % n;
                // 箱子移动到目标位置了
                if (grid[curBx][curBy] == 'T') return dis[spos][bpos];

                // 玩家向四个方向移动
                for (int i = 0; i < 4; ++i) {
                    int nxtSx = curSx + dir[i], nxtSy = curSy + dir[i + 1];
                    int newSpos = nxtSx * n + nxtSy;
                    // 玩家位置不合法
                    if (!check(grid, m, n, nxtSx, nxtSy)) continue;

                    if (nxtSx == curBx && nxtSy == curBy) {
                        // 可以移动箱子
                        int nxtBx = curBx + dir[i], nxtBy = curBy + dir[i + 1];
                        int newBpos = nxtBx * n + nxtBy;
                        // 位置不合理 or 当前位置已访问过
                        if (!check(grid, m, n, nxtBx, nxtBy)
                                || dis[newSpos][newBpos] <= dis[spos][bpos] + 1) {
                            continue;
                        }

                        dis[newSpos][newBpos] = dis[spos][bpos] + 1;
                        assQue.offer(new int[]{newSpos, newBpos});
                    } else {
                        // 位置已经访问过
                        if (dis[newSpos][bpos] <= dis[spos][bpos]) continue;

                        dis[newSpos][bpos] = dis[spos][bpos];
                        que.offer(new int[]{newSpos, bpos});
                    }
                }
            }
            que = assQue;
        }

        return -1;
    }

    /**
     * 不越界且不在墙壁上
     */
    private boolean check(char[][] grid, int m, int n, int x, int y) {
        return 0 <= x && x < m && 0 <= y && y < n && grid[x][y] != '#';
    }
}
